package com.datastructure.test.intersectionofintervals;

import java.util.ArrayList;

public class IntersectionOfIntervals {

    public static void main(String[] args) {
        IntersectionOfIntervals intersectionOfIntervals = new IntersectionOfIntervals();
        ArrayList<ArrayList<Integer>> first = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(0);
        list1.add(2);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(5);
        list2.add(10);
        ArrayList<Integer> list3 = new ArrayList<>();
        list3.add(11);
        list3.add(13);
        first.add(list1);
        first.add(list2);
        first.add(list3);
        ArrayList<ArrayList<Integer>> second = new ArrayList<>();
        ArrayList<Integer> list4 = new ArrayList<>();
        list4.add(1);
        list4.add(3);
        ArrayList<Integer> list5 = new ArrayList<>();
        list5.add(5);
        list5.add(11);
        second.add(list4);
        second.add(list5);
        ArrayList<ArrayList<Integer>> intersectionofintervals = intersectionOfIntervals.intersectionofintervals(first, second);
        System.out.println(intersectionofintervals);
    }

    public ArrayList<ArrayList<Integer>> intersectionofintervals (ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> temp;
        int left;
        int right;
        int leftTemp;
        int rightTemp;
        for (ArrayList<Integer> fir : first) {
            left = fir.get(0);
            right = fir.get(1);
            for (ArrayList<Integer> sec : second) {
                leftTemp = sec.get(0);
                rightTemp = sec.get(1);
                if(leftTemp>right){
                    continue;
                }
                if (leftTemp >= left && rightTemp >= right) {
                    temp = new ArrayList<>(2);
                    temp.add(leftTemp);
                    temp.add(right);
                    res.add(temp);
                }
                if (leftTemp > left && rightTemp < right) {
                    res.add(sec);
                }
                if (leftTemp < left && rightTemp > right) {
                    res.add(fir);
                }
                if (leftTemp <= left && rightTemp > left && rightTemp < right) {
                    temp = new ArrayList<>(2);
                    temp.add(left);
                    temp.add(rightTemp);
                    res.add(temp);
                }
                if (leftTemp < left && rightTemp == right) {
                    temp = new ArrayList<>(2);
                    temp.add(left);
                    temp.add(rightTemp);
                    res.add(temp);
                }
                if (rightTemp == left) {
                    temp = new ArrayList<>(2);
                    temp.add(rightTemp);
                    temp.add(rightTemp);
                    res.add(temp);
                }
            }
        }
        return res;
    }
}
